
//85.最大矩阵
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();

        auto r_max=[&](int level)
        {
            vector<int> nums(n);  //统计从level层开始向下连续1的长度
            for(int i=0;i<n;i++)
            {
                int j=level;
                while(j<m&&matrix[j][i]=='1') j++;
                nums[i]=j-level;
            }

            //以下与84题代码一样
            //向左向右统计可以扩展的最大长度
            vector<int> right(n,n);
            stack<pair<int,int>> st;
            for(int i=0;i<n;i++)
            {
                while(!st.empty()&&st.top().first>nums[i])
                {
                    int index=st.top().second;
                    right[index]=i;
                    st.pop();
                }
                st.push({nums[i],i});
            }
            while(!st.empty()) st.pop();
            vector<int> left(n,-1);
            for(int i=n-1;i>=0;i--)
            {
                while(!st.empty()&&st.top().first>nums[i])
                {
                    int index=st.top().second;
                    left[index]=i;
                    st.pop();
                }
                st.push({nums[i],i});
            }       
            int each=0;
            for(int i=0;i<n;i++)
                each=max(each,(right[i]-left[i]-1)*nums[i]);
            return each;
        };

        int ret=0;
        for(int k=0;k<m;k++)  //对每一层都进行统计
            ret=max(ret,r_max(k));
        
        return ret;
    }
};